//
// Created by Tan Ke on 2023/12/15.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 使用recordmap记录字符串text1和字符串text2在不同长度是的最大子字符串长度,
 * 例如recordmap[i][j]就表示text1[0...i], text2[0...j]的最大子字符串
 * recordmap[text1Len-1][text2Len-1]就是text1, text2的最大子字符串长度
 *
 * 初始化时: recordmap[0][0...text2Len-1], recordmap[0...text1Len-1]的值是可以初始化的
 * 对于recordmap[i][j], 它的最大值为:
 * 1). 如果text1[i] == text1[j], 那么recordmap[i][j] = recordmap[i-1][j-1] + 1;
 * 2). 否则: recordmap[i][j] = max(recordmap[i-1][j], recordmap[i][j-1]);
 */

int longestCommonSubsequence(char* text1, char* text2)
{
    int i, j;
    int** recordMap = (int**)malloc(sizeof(int*) * strlen(text1));
    for (i = 0; i < strlen(text1); i ++) {
        recordMap[i] = (int*)malloc(sizeof(int) * strlen(text2));
        for (j = 0; j < strlen(text2); j ++) {
            recordMap[i][j] = 0;
        }
    }

    /* 初始化 recordmap[0][0...text2Len-1] */
    for (j = 0; j < strlen(text2); j ++) {
        if (text1[0] == text2[j]) {
            break;
        }
    }
    while (j < strlen(text2)) {
        recordMap[0][j] = 1;
        j += 1;
    }
    /* -------------------------------- */

    /* 初始化 recordmap[0...text1Len-1][0] */
    for (i = 0; i < strlen(text1); i ++) {
        if (text1[i] == text2[0]) {
            break;
        }
    }
    while (i < strlen(text1)) {
        recordMap[i][0] = 1;
        i += 1;
    }
    /* -------------------------------- */

    for (i = 1; i < strlen(text1); i ++) {
        for (j = 1; j < strlen(text2); j ++) {
            if (text1[i] == text2[j]) {
                recordMap[i][j] = recordMap[i-1][j-1] + 1;
            } else {
                if (recordMap[i-1][j] > recordMap[i][j-1]) {
                    recordMap[i][j] = recordMap[i-1][j];
                } else {
                    recordMap[i][j] = recordMap[i][j-1];
                }
            }
        }
    }

    return recordMap[strlen(text1) - 1][strlen(text2) - 1];
}

int main(void)
{
    char* text1 = "pmjghexybyrgzczy";
    char* text2 = "hafcdqbgncrcbihkd";

    printf("%d\n", longestCommonSubsequence(text1, text2));

    return 0;
}